分析：什麼時候該使用Backtracking

當題目要求output中有多種解答時，使用backtracking是個不錯的選擇。
為了能得到多種solution並且回傳，使用遞迴來實作是很直觀的想法，另外還需要能夠接納這些solution的資料結構（array, list...）

先實際看一題吧

Leetcode 78. Subset
題目敘述：給定一個整數的array，得到這個array所有的subset。
Example:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

一個很直觀的想法是我們需要「挑選」出nums中的一些數字把他放到新的array中成為一個subset，「重複」這個動作數次來找出所有的subset。

Backtracking 1+3要素

上面提到的很直觀的想法，就存在著製作出backtracking algorithm template很大的提示。

• 「重複」提示了使用遞迴，可以達成這個行為。

1. 目標（Goal）：要得到一個solution需要的條件。
2. 選擇（Choose）：根據情境，我們可以從input中選取的元素。
3. 限制（Constraint）[Optional]：根據題目（任務）去限制部分選項，不一定每個任務都有。

將這些要素拼湊起來就可以形成一個backtracking template

def backtrack(input):
    if (goal reached):
        there is a solution in the list, store it
        return
    
    choose an element from input and add it to the list
    backtrack(input)
    pop the element from the list

來解題吧

我們重新回到Leetcode 78. subset根據backtracking 三要素來寫code。
首先先釐清這三要素在這題上實際代表著什麼：

1. Goal：當我們利用遞迴拜訪完array中的最後一個元素時代表找出一個solution了。
2. Choose：很明顯我們可以去決定是否要去選擇array中的某個數字。
3. Constraint：無。

我們可以利用decision tree來可視化上述的1+3要素，這對於解決和backtracking有關的問題時很有幫助。

以下使用了python將Leetcode 78.的實際解答實作出來。利用python中的list以及inner function對於解題來說非常方便。inner function可以直接存取到外部變數。

但是要注意的是，在達成Goal將solution存放到res中時，應該存放的是拷貝的list instance ，因為sol這個list會被許多個recursive call的subsets函數存取。若是直接將sol 的reference存放到res中這裡面的值就會被之後的recursive call的subsets函數所改寫。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        sol = []

        def backtrack(i):
            # Goal
            if i == len(nums):
                res.append(sol.copy())
                return
            
            # choose nums[i]
            sol.append(nums[i])
            backtrack(i + 1)
            sol.pop()

            # not choose nums[i]
            backtrack(i + 1)
        
        backtrack(0)
        return res

Follow up

Leetcode 90. Subsets II
現在input array可能有重複的數字。

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

我們馬上利用backtracking三要素去分析題目，

1. Goal：當我們利用遞迴拜訪完array中的最後一個元素時代表找出一個solution了。
2. Choose：很明顯我們可以去決定是否要去選擇array中的某個數字。
3. Constraint：如果決定不再選擇某個數字，那麼從這個分歧點開始永遠不會再出現這個數字了。

為了要解決這個問題，我們首先需要將input array排序。另外，為了能夠符合constraint，利用迴圈來找出與目前的數字不同的值的index。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        sol = []
        
        def backtrack(i):
            if i == len(nums):
                res.append(sol.copy())
                return
            
            # choose nums[i]
            sol.append(nums[i])
            backtrack(i + 1)
            sol.pop()

            # not choose nums[i] and this value won't appear again in the path
            # constraint
            while i + 1 < len(nums) and nums[i] == nums[i + 1]:
                i += 1
            
            backtrack(i + 1)
        
        nums.sort()
        backtrack(0)
        return res

後記：被朋友慫恿參加IT鐵人賽，這是我在這個網站的第一篇文章。主要是想分享關於coding interview 的一些自己解題的手段給需要的人。
如果有哪邊說明有誤或不清楚，歡迎任何指正和建設性批評。明天繼續努力，peace out✌🏻。